package by2019;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
 * 将n个皇后放在n*n的棋盘上，并且使皇后彼此之间不能相互攻击
 * 皇后的攻击范围是横竖撇那
 * 
 * 递归每一层，在每一层中遍历列
 * 如果有皇后放入，就把皇后能够攻击的位置存入list
 * 在每一次遍历的时候就判断该位置是否存在于list之中
 * 
 */
public class N皇后问题 {
	
		static List<int[]> iList = new ArrayList<int[]>() ;
		static List<List<String>> reList = new ArrayList<List<String>>();
		static int count = 0 ;
	
	public static void main(String[] args) {
		
		long time = System.currentTimeMillis() ;
		System.out.println(solveNQueens(8));
		long time2 = System.currentTimeMillis() ;
		System.out.println("用时：");
		System.out.println(time2-time);
	}
	
	public static List<List<String>> solveNQueens(int n) {
		Set<Integer> lie = new HashSet<Integer>();
		Set<Integer> pie = new HashSet<Integer>();
		Set<Integer> na = new HashSet<Integer>();
		
		int[] a = new int[n];
		DFS(n, 0, a, lie, pie, na);
		
		return  reList;
    }
	//x是第几行，y是第几列
	public static void DFS(int n, int x, int[] a, Set<Integer> lie, Set<Integer> pie, Set<Integer> na){
		if(x>=n) {
			iList.add(a);
			//System.out.println("完成站位："+Arrays.toString(a));
			//System.out.println("\n站位后的iList：");
			//popList(iList) ;
			//取出位置的数组
			for(int i=0;i<iList.size();i++) {
				int[] wz = iList.get(i);
				//取出reList的每个List<String>，行
				for(int j=0;j<n;j++) {
					List<String> list = new ArrayList<String>();
					StringBuilder sb = new StringBuilder() ;
					//给每个List<String>赋值，给它的的index行的第value个位置赋上Q，其他位置赋上0
					//列
					for(int k=0;k<n;k++) {
						if(k==wz[j]) {
							sb.append('Q') ;
						}
						sb.append('.');
					}
					list.add(sb.toString());
					reList.add(list);
				}
			}
			return ;
		}
		
		for(int y=0;y<n;y++) {
			if(pie.contains(y+x) || na.contains(x-y) || lie.contains(y))
				continue ;
			lie.add(y) ;
			pie.add(x+y) ;
			na.add(x-y) ;
			a[x] = y ;
			
			DFS(n, x+1, a, lie, pie, na) ;
			
			lie.remove(y);
			pie.remove(x+y);
			na.remove(x-y);
			//System.out.println("第"+x+"层进行了回滚");
			//System.out.println("此时的iList : ");
			//popList(iList);
			a[x] = -1 ;
		}
		
	}
	
	public static void popList(List<int[]> list) {
		for(int[] i : iList) {
			System.out.print(Arrays.toString(i)+" ");
		}
	}
	
	//判断n皇后问题是否有解
	public static void solveNQueensX(int n) {
		Set<Integer> lie = new HashSet<Integer>();
		Set<Integer> pie = new HashSet<Integer>();
		Set<Integer> na = new HashSet<Integer>();
		
		DFSx(n, 0, lie, pie, na);
		
	}
	public static void DFSx(int n, int x, Set<Integer> lie, Set<Integer> pie, Set<Integer> na){
		//System.out.println("进入"+x+"层");
		if(x>=n) {
			System.out.println("有解");
			return ;
		}
		
		
		for(int y=0;y<n;y++) {
			//System.out.println("进入循环"+x);
			if(pie.contains(y+x) || na.contains(x-y) || lie.contains(y))
				continue ;
			if(x==1)
				count++ ;
			lie.add(y) ;
			pie.add(x+y) ;
			na.add(x-y) ;
			
			DFSx(n, x+1, lie, pie, na) ;
			
			lie.remove(y);
			pie.remove(x+y);
			na.remove(x-y);
			//System.out.println("第"+x+"层进行了回滚");
			//System.out.println("此时的iList : ");
			//popList(iList);
		}
		count++ ;
		if(count>=n  && x==0) {
			System.out.println("无解,count="+count+" n="+n);
			return ;
		}
		//System.out.println("over,count="+count+" x="+x+" n="+n);
	}
}
